2563번 색종이

Day7 7단계 20231025
(해결 날짜 : 20231026)
( 다른 사람의 아이디어로 풀었다. 다음엔 내 아이디어로 풀어보자. )

• 중복되는 영역 제거할 방법 찾기
  • 그런데 종이가 2장 겹친다면 1구역, 3장 겹친다면 1~3구역까지도 겹칠 수 있고, 정확한 범위를 잡기가 너무 어렵다.
• 결국 이 방법은 사용하지 못했다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int num = Integer.parseInt(br.readLine());
		int[][] a = new int[num][2];
		int xdup = 0;
		int ydup = 0;
		int dupArea = 0;
		
		for (int i = 0; i < num; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < 2; j++) {
				a[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i = 0; i < num - 1; i++) {
			for (int j = i + 1; j < num; j++) {
				if (Math.abs(a[j][0] - a[i][0]) < 10 && Math.abs(a[j][1] - a[i][1]) < 10) {
					xdup = Math.min(a[i][0], a[j][0]) + 10 - Math.max(a[i][0], a[j][0]);
					ydup = Math.min(a[i][1], a[j][1]) + 10 - Math.max(a[i][1], a[j][1]);
					dupArea += (xdup) * (ydup);
				}
			}
		}
		System.out.println(100 * num - dupArea);
		br.close();
	}
}

• 다른 사람들 풀이 1
  • 만약 색종이가 3번 이상 겹치면 일일이 케이스를 확인하기도 어렵다. 역으로 각 정사각형이 커버하는 영역만을 합산하는 방법을 찾아보자
• 다른 사람들 풀이 2
  • 좌표상의 각 점을 배열의 위치로 저장하고, 그 위치에 값을 true와 false로 저장한다. 색종이가 차지하는 위치라면 true, 아무 색종이도 없으면 false(기본값)로 저장해서 총 범위에서 배열 내에 true의 개수를 구한다.
  • 흰 종이의 좌표는 0 부터 100까지 있어야 하므로, 전체 흰 종이의 x,y 좌표는 101개가 된다.
  • 색종이는 시작 지점 a~ (a+ 10)까지 범위를 차지하는데, 중요한 건 우리가 사용한 게 넓이가 아닌 점의 좌표기 때문에 색종이들의 경계면에만 걸치고 겹치지 않는 경우를 고려해보자면 실제 범위는 a~ (a+ 9)까지만 넣어야 한다.(개인적 의견)
  • https://propercoding.tistory.com/241

import java.io.*;
import java.util.*;
// code idea from https://propercoding.tistory.com/241
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		boolean[][] paper = new boolean[101][101];
		int num = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < num; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			for (int j = x; j < x + 10; j++) {
				for (int k = y; k < y + 10; k++) {
					paper[j][k] = true;
				}
			}
		}
		int numTrue = 0;
		for(boolean[] b1 : paper) {
			for(boolean b2 : b1) {
				if(b2) {numTrue++;}
			}
		}
		System.out.println(numTrue);
	}
}